//https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=13&tqId=23454&ru=%2Fpractice%2F435fb86331474282a3499955f0a41e8b&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13
//问题：1.之字形打印矩阵；reverse函数使用！队列+层序遍历！
//思路：1.层序遍历，每层都保存结果；2.当前队列的size就是当前层的个数；3.偶数层逆序打印，奇数层顺序打印；
//     2.



#include <algorithm>
#include <climits>
#include <queue>
#include <vector>

using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > res;
        if (!pRoot)
            return res;
        queue<TreeNode*> q; // 定义队列
        q.push(pRoot); // 根结点入队列
        bool reverse_flag = false;

        while (!q.empty()) {
            vector<int> arr; // 定义数组存储每一行结果
            int size = q.size(); // 当前队列长度
            for (int i = 0; i < size; i++) {
                TreeNode* tmp = q.front(); // 队头元素
                q.pop();
                if (!tmp) // 空元素跳过
                    continue;
                q.push(tmp->left); // 左孩子入队列
                q.push(tmp->right); // 右孩子入队列
                
                // 从左至右打印
                arr.push_back(tmp->val);
               
            }
            if (reverse_flag) {
                reverse(arr.begin(),arr.end());
            }
            reverse_flag = !reverse_flag; // 下一层，改变打印方向
            if (!arr.empty())
                res.push_back(arr); // 放入最终结果
        }
        return res;
    }
};